// insert here for test
#include <vector>
// insert end
#include <iostream>
#include <ctime>    // clock()
#include <cstdlib> // bsearch()  snprintf()
#include <string>

#include <algorithm> // find() sort()

#include "test.h"

using std::cin;
using std::cout;
using std::endl;

using std::vector;
using std::string;

void test(long& value, bool use_cap = false) {
    cout << endl
        << "test_array()..."
        << endl;
    
    // 声明一个 vector 容器，其中元素类型为 string
    vector<string> vec;
    if (use_cap) {
        // reserve 给容器充足的空间，确保不进行扩容操作
        vec.reserve(value+1);
    }
    // 后续测试的string 空间，为了生成一个随机的字符串
    char buf[10];

    // 启动时间
    clock_t timeStart = clock();

    // 生成随机字符串并且存入 vector 容器中
    for (long i = 0; i < value; ++i) {
        // 内存不足，处理异常
        try {
            snprintf(buf, 10, "%d", rand());
            vec.push_back(string(buf));

            // vec 内存分配
            // 如果当前 capacity == size ， capacity = capacity * 2
            // 若 capacity 无法实现，内存不足，抛出异常
        } catch (std::exception &err) {
            // 一般内存不足
            cout << "i = " << i << " " << err.what() << endl;
            // generate a core dump --> 终止程序
            abort();
        }
    }

    cout << "insert use time: " << transformClockSeconds(clock() - timeStart) << "s" << endl;
    cout << "vector.size(): " << vec.size() << endl;
    cout << "vector.capacity(): " << vec.capacity() << endl; // capacity 是容器大小 , size 是元素实际个数
    cout << "vector.front(): " << vec.front() << endl;
    cout << "vector.back(): " << vec.back() << endl;
    cout << "vector.data(): " << vec.data() << endl;

    // 查找
    string target = get_a_target_string();
    // std::find
    {
        cout << "std::find() " << endl;
        cout << "see it in  https://www.cplusplus.com/reference/algorithm/find/?kw=find " << endl;
        timeStart = clock();
        auto pItem = std::find(vec.begin(), vec.end(), target);
        cout << "std::find() use time: " << transformClockSeconds(clock() - timeStart) << "s" << endl;

        if (pItem != vec.end()) {
            cout << "found, " << *pItem << endl;

            // 查看是否找到最后一个数字
            if (pItem == (vec.end() -1)) {
                cout << "found back!" << endl;
            }

        } else {
            cout << "sorry, not found" << endl;
        }
    }

    {
        cout << "sort + bsearch" << endl;
        // 先排序，后二分查找
        clock_t ttimeStart = clock();
        timeStart = ttimeStart;
        sort(vec.begin(), vec.end());
        cout << "sort use time: " << transformClockSeconds(clock() - timeStart) << "s" << endl;
        timeStart = clock();
        string* pItem = (string*)bsearch(&target, (vec.data()), (vec.size()), sizeof(string), compareStrings);
        cout << "bsearch use time: " << transformClockSeconds(clock() - timeStart) << "s" << endl
            << "sort & bsearch use time: " << transformClockSeconds(clock() - ttimeStart) << "s" << endl;

        if (pItem != nullptr) {
            cout << "found " << *pItem << endl;
        } else {
            cout << "sorry, not found " << endl;
        }
    }
}

int main(void) {
    long value;
    cout << "Please input a number for vector size: ";
    cin >> value;

    cout << "dynamic: ----" << endl;
    test(value);

    cout << endl << "no dynamic: ----" << endl;
    test(value, true);

    return 0;
}

